/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 /*
 date:20210328 12:45pm
 key:中序遍历的时候用一个vector装，成员变量i记录了下表，看vector的大小指定有没有下一个。但这样提前遍历是复杂度O(N).
    想考的是中序遍历的迭代，一次next迭代一次。
 */
class BSTIterator {
public:
    vector<int>V;
    int i=-1;
    void middle(TreeNode* root) 
    {
    if(root!=nullptr)
    {
        middle(root->left); 
        V.push_back(root->val);
        cout<<root->val;
        middle(root->right); 
    }

    }
    BSTIterator(TreeNode* root) {
       
    //指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素
    //V.push_back(-1);
    if(root!=nullptr)
    {
        middle(root);
    }
    }
    
    int next() 
    {
        i++;
        return V[i];
    }
    
    bool hasNext() {
    if(i+1<V.size())
    {
        return 1;
    }
    return 0;
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */